package 树.BST;

public class 有序链表转换二叉搜索树_109 {
    public static void main(String[] args) {
        ListNode head = new ListNode(-10, -3, 0, 5, 9);
        System.out.println(sortedListToBST(head).toString());
    }

    public static TreeNode sortedListToBST(ListNode head) {
        ListNode p = head, q = head, pre = null;
        //base case
        if (head == null) {//head为空，就是空树
            return null;
        }
        if (head.next == null) {//head只有一个节点，返回head
            return new TreeNode(head.val);
        }
        // 快慢指针找中心节点
        while (q != null && q.next != null) {//快指针==null，即到达了链表尾部，这时候慢指针刚好到达链表中间位置，可以自己举例试试，因为快指针一次走两步，慢的一次走一步
            pre = p;//保存慢指针之前的那个值，因为到时候慢指针就是中间，pre就是左子树
            p = p.next;
            q = q.next.next;
        }
        pre.next = null;//这句话是用来切割链表的，将head从pre切开,head变为pre左边部分,p为pre右边部分。

        // 以升序链表的中间元素作为根节点 root，递归的构建 root 的左子树与右子树。
        TreeNode root = new TreeNode(p.val);
        root.left = sortedListToBST(head);//左子树，因为head已经被pre给切割了，只要遍历到pre.next是null，就会返回null。这样就保证了只有左子树
        root.right = sortedListToBST(p.next); //右子树
        return root;

    }
}
